1. Databases
2. Proof database
3. Inequality of the power of a sum and the sum of the power

Inequality of the power of a sum and the sum of the power

Given the integer power of a sum, it is constrained by the inequality

\begin{equation} \left( \sum_{i = 1}^n x_i \right)^p \leq n^{p - 1} \sum_{i = 1}^n x_i^p \end{equation}

Proof

By induction, let's first consider

\begin{equation} \left( \sum_{i = 1}^n x_i \right)^1 = n^{1 - 1} \sum_{i = 1}^n x_i^1 \end{equation}

As it is equal, it is also trivially true that it is inferior or equal. Now, assuming it true for $p$, let's check for $p + 1$ :

\begin{eqnarray} \left( \sum_{i = 1}^n x_i \right)^{p + 1} &=& \left( \sum_{i = 1}^n x_i \right)^{p} \left( \sum_{i = 1}^n x_i \right)\\ &\leq& n^{p - 1} \sum_{j = 1}^n \sum_{i = 1}^n \left[ x_i^p x_j \right] &=& n^{p - 1} \left[ \sum_{i = 1}^n x_i^{p + 1} + \sum_{i \neq j} x_i^p x_j \right] \end{eqnarray}